#include <iostream>
// #include "DLinkList.h"
// #include "./01_lineList/DLinkList.h"
using namespace std;

// 循环单、双链表

/// @brief 单链表节点的定义
typedef struct LNode
{                       // 定义单链表节点类型
    int data;           // 每个节点存放一个数据元素
    struct LNode *next; // 指针指向下一个节点
} LNode, *LinkList;

/// @brief 双链表
typedef struct DNode // 定义双链表节点类型
{
    int daya;                   // 数据域
    struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;

/// @brief 初始化一个循环单链表
/// @param L
/// @return
bool InitLinkList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
    {
        return false;
    }
    L->next = L;
    return true;
}

/// @brief 判断循环单链表是否为空
/// @param L
/// @return
bool Empty(LinkList L)
{
    if (L->next == L)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 判断节点p是否为循环单链表的表尾节点
/// @param L
/// @param p
/// @return
bool isTail(LinkList L, LNode *p)
{
    if (p->next == L)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 初始化空的循环双链表
/// @param L
/// @return
bool InitDLinkList(DLinkList &L)
{
    L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
    if (L == NULL)
    { // 内存不足，分配失败
        return false;
    }
    L->prior = L; // 头结点的prior指向头结点
    L->next = L;  // 头结点的next指向头结点
    return true;
}

/// @brief 判断循环双链表是否为空
/// @param L
/// @return
bool Empty(DLinkList L)
{
    if (L->next == L)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 判断节点p是否为循环单链表的表尾节点
/// @param L
/// @param p
/// @return
bool isTail(DLinkList L, DNode *p)
{
    if (p->next == L)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 在p节点之后插入s节点
/// @param p
/// @param s
/// @return
bool InsertNextDNode(DNode *p, DNode *s)
{
    s->next = p->next; // 将节点*s插入到节点*p之后
    p->next->prior = s;
    s->prior = p;
    return true;
}

/// @brief 双链表的删除：删除p的后继节点
/// @param p
/// @param q
/// @return
bool DeleteNextDNode(DNode *p, DNode *q)
{
    // 删除p节点的后继节点q
    p->next = q->next;
    q->next->prior = q;
    free(q);
    return true;
}
